package com.kristin.sort;

import java.util.Arrays;

/**
 * 归并排序。
 * 分组，将分组先进行排序，然后进行合并。
 *
 */
public class MergeSort {


    public void sort(int arrs[]) {

    }

    /**
     *
     * @param arrs 待排序数组
     * @param left 左下标
     * @param right 右下标
     */
    public void mergeSort(int[] arrs, int left, int right) {
        if(left == right) {
            return;
        }
        int length = right - left + 1;
        int middle = left + length/2;
        mergeSort(arrs, left, middle - 1);
        mergeSort(arrs, middle, right);
        merge(arrs, left, middle, right);
    }


    public void merge(int[] arrs, int begin , int middle , int end){
        int[] temp = new int[end - begin + 1];
        int tempIndex = 0;
        int left = begin;
        int right = middle;
        while(left < middle  && right <= end ) {
            if(arrs[left] < arrs[right]) {
                temp[tempIndex] = arrs[left];
                left++;
            } else {
                temp[tempIndex] = arrs[right];
                right++;
            }
            tempIndex ++;
        }

        while(left < middle) {
            temp[tempIndex] = arrs[left];
            left++;
            tempIndex ++;
        }

        while(right <= end) {
            temp[tempIndex] = arrs[right];
            right++;
            tempIndex ++;
        }

        for(int i = 0 ; i <temp.length; i++) {
            arrs[begin + i] = temp[i];
        }

    }

}



